package com.zx._12_算法.字节跳动面试题;

import com.zx._12_算法.Nums;

/**
 * 素数一般指质数。质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数
 * 思路1：新定义一个数组，用来保存素数。排序后读取位置
 * 思路2: 使用原数组，将素数转移到左边，然后只排序左边
 * 思路3：使用插入排序。一边遍历一边查找素数，一边排序
 */
public class 数组中第K大的素数 {

    public static void main(String[] args) {
        fn3(2);
    }

    public static void main1(String[] args) {
        int[] nums = Nums.nums;
        // 数组中保存素数的索引
        int curtor = 0;
        // 将素数放最最边
        for (int i = 0; i < nums.length; i++) {
            // 判断素数
            if (isSuShu(nums[i])) {
                swap(nums, curtor, i);
                // 顺便排序，只排序 0~curtor, 插入排序

                int needNum = nums[curtor];
                int needIdx = 0;
                for (int j = curtor - 1; j >= 0; j--) {
                    if (nums[j] < needNum) {
                        nums[j + 1] = nums[j];
                    } else {
                        needIdx = j + 1;
                        break;
                    }
                }
                nums[needIdx] = needNum;

                // 下一个需要保存的位置
                curtor++;
            }
        }
        Nums.print();

        int k = 1;

        System.out.println(nums[k - 1]);
    }


    public static void fn1(int k) {
        int[] nums = Nums.nums;

        int[] res = new int[nums.length];
        int resIdx = 0;
        for (int i = 0; i < nums.length; i++) {
            if (isSuShu(nums[i])) {
                res[resIdx++] = nums[i];
            }
        }

        Nums.print(res);

        int size = resIdx;
        if (k > size) {
            System.out.println("没有数量为k的素数，k=" + k);
            return;
        }
        // 排序，局部排序即可。// 冒泡、选择、插入、堆排序、插入排序
        for (int i = 0; i < size; i++) {
            int maxIdx = i;
            for (int j = i + 1; j < size; j++) {
                if (res[j] > res[maxIdx]) {
                    maxIdx = j;
                }
            }
            if (maxIdx != i) {
                swap(res, i, maxIdx);
            }
            if (i == k - 1) {
                break;
            }
        }
        Nums.print(res);
        System.out.println(res[k - 1]);
    }

    public static void fn2(int k) {
        int[] nums = Nums.nums;

        int resIdx = 0;
        for (int i = 0; i < nums.length; i++) {
            if (isSuShu(nums[i])) {
                swap(nums, resIdx++, i);
            }
        }
        Nums.print(nums);

        int size = resIdx;
        if (k > size) {
            System.out.println("没有数量为k的素数，k=" + k);
            return;
        }
        // 排序，局部排序即可。// 冒泡、选择、插入、堆排序、插入排序
        for (int i = 0; i < size; i++) {
            int maxIdx = i;
            for (int j = i + 1; j < size; j++) {
                if (nums[j] > nums[maxIdx]) {
                    maxIdx = j;
                }
            }
            if (maxIdx != i) {
                swap(nums, i, maxIdx);
            }
            if (i == k - 1) {
                break;
            }
        }
        Nums.print(nums);
        System.out.println(nums[k - 1]);
    }

    public static void fn3(int k) {
        int resIdx = 0;
        int[] nums = Nums.nums;

        for (int i = 0; i < nums.length; i++) {
            // 找到素数，将其放到resIdx位置上
            if (isSuShu(nums[i])) {
                swap(nums, resIdx, i);
                // 然后，对0~resIdx范围的数据进行插入排序
                // resIdx就是需要插入的数字
                int needNum = nums[resIdx];
                int j = resIdx - 1;
                for (; j >= 0; j--) {
                    if (nums[j] < needNum) {
                        nums[j + 1] = nums[j];
                    } else {
                        break;
                    }
                }
                nums[j + 1] = needNum;
                resIdx++;
            }
        }
        Nums.print(nums);
        System.out.println(nums[k - 1]);

    }


    public static void swap(int[] nums, int a, int b) {
        int t = nums[a];
        nums[a] = nums[b];
        nums[b] = t;
    }

    // 判断素数
    public static boolean isSuShu(int num) {
        boolean is = true;
        // 这三个被定义为素数
        if (num == 0 || num == 1 || num == 2) {
            return true;
        }
        if (num % 2 == 0) {
            // 偶数一定不是素数
            is = false;
        } else {
            // 找到
            for (int i = 3; i < num; i++) {
                if (num % i == 0) {
                    is = false;
                    break;
                }
            }
        }
        return is;
    }
}
